home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 May: Tool Chest / Developer CD Series May 1996 (Tool Chest) (Apple Computer) (1996).iso / Tool Chest / Development Tools & Languages / Dylan Related / Mindy / Mindy 1.2 - Mac PPC / doc / collection-extensions.txt < prev    next >
Encoding:
Text File  |  1995-03-15  |  9.9 KB  |  218 lines  |  [TEXT/MMCC]
  1.                       The Collection-Extensions library
  2.                       =================================
  3.  
  4.   Copyright (c) 1994  Carnegie Mellon University
  5.   All rights reserved.
  6.  
  7.   The various modules in this library contain a few new types and operations
  8.   which are compatible with the collection types specified in the Dylan
  9.   Interim Reference Manual, but which are not part of that specification.  
  10.  
  11.   Users of Mindy 1.1 should be aware that the string-searching functions of
  12.   the string-search module have been moved to the String-extensions library.
  13.   The collection-extensions module "string-search" has for that reason been
  14.   renamed "vector-search".  The semantics of the moved functions have been
  15.   changed, so string-search users are advised to read the String-extensions
  16.   documentation.  
  17.  
  18.   It is to be expected that more collection types will appear in time, and
  19.   they will likely be added to this library.  This may also result in
  20.   reorganizations which could force incompatible changes to the existing
  21.   modules.  We hope to minimize such imcompatibilities and, when forced to
  22.   them, will include sufficient information to facilitate conversion of
  23.   existing code.  
  24.  
  25.   The particular modules provided at present are:  
  26.  
  27.   heap 
  28.       Provides <heap>, a popular data structure for priority queues.  The
  29.       semantics are basically those of a sorted sequence, with particularly
  30.       efficient implementations of add!, first, and pop (i.e.
  31.       "remove-first").  
  32.   self-organizing-list 
  33.       Provides "self-organizing lists".  These explicit key collections
  34.       provide roughly the semantics of hash tables, but use a probabilistic
  35.       implementation which provides O(n) worst case performance but can
  36.       provide very fast constant time access in the best case.  
  37.   subseq 
  38.       Provides "subsequences", which represent an aliased reference to some
  39.       part of an existing sequence.  These are analogous to slices (in Ada or
  40.       Perl) or displaced arrays (in Common Lisp).  Subsequences are
  41.       themselves subclasses of <sequence>, and can therefore be passed any
  42.       <collection> or <sequence> operation.  
  43.   vector-search 
  44.       Provides a small assortment of specialized operations for searching and
  45.       modifying <vector>s.  These operations are analogous to existing
  46.       collection operations but provide keywords and efficiency improvements
  47.       which are meaningful only within the more limited domain. 
  48.  
  49. Heap
  50. ----
  51.   A heap is an implementation of the abstract data type "sorted list". A heap
  52.   is a sorted sequence of items.  Most likely the user will end up writing
  53.   something like 
  54.  
  55.   define class <heap-item> (<object>);
  56.     slot priority;
  57.     slot data;
  58.   end class <heap-item>;
  59.  
  60.   with appropriate methods defined for < and =. The user could, however, have
  61.   simply a sorted list of integers, or have some item where the priority is
  62.   an integral part of the item itself.  
  63.  
  64.   make on heaps supports the less-than: keyword, which supply the heap's
  65.   comparison and defaults to <.  
  66.  
  67.   Heaps support all the usual sequence operations. The most useful ones:  
  68.  
  69.        push(heap, item) => updated-heap
  70.        pop(heap)        => smallest-element
  71.        first(heap)      => smallest-element
  72.        second(heap)     => second-smallest-element
  73.        add!(heap, item) => updated-heap
  74.        sort, sort!      => sorted-sequence
  75.  
  76.   These are all "efficient" operations (defined below).  As with <deque>,
  77.   push is another name for add!, and does exactly the same thing except that
  78.   push doesn't accept any keywords.  sort and sort! return a sequence that's
  79.   not a heap. Not necessarily efficient but useful anyhow:  
  80.  
  81.        add-new!(heap, item, #key test:, efficient:) => updated-heap
  82.        remove!(heap, item, #key test:, efficient:) => updated-heap
  83.        member?(heap, item, #key test:, efficient:) => <boolean>
  84.  
  85.   The efficient: keyword defaults to #f. If #t, it uses the
  86.   random-iteration-protocol (which is considerably more efficient, but isn't
  87.   really standard behavior, so it had to be optional).  Conceivably most
  88.   sequence methods could support such a keyword, but they don't yet.  
  89.  
  90.   The user can use element-setter or the iteration protocol to change an item
  91.   in the heap, but changing the priority of an item is an error and Bad
  92.   Things(tm) will happen. No error will be signaled.  Both of these
  93.   operations are very inefficient.  
  94.  
  95.   Heaps are NOT <stretchy-collection>s, although add! and pop can magically
  96.   change the size of the heap.  
  97.  
  98.   Efficiency: Approximate running times of different operations are given
  99.   below: (N is the size of the heap) 
  100.  
  101.       first, first-setter                             O(1)
  102.       second (but not second-setter)                  O(1)
  103.       size                                            O(1)
  104.       add!                                            O(lg N)
  105.       push                                            O(lg N)
  106.       pop(heap)                                       O(lg N)
  107.       sort, sort!                                     O(N * lg N)
  108.       forward-iteration-protocol          
  109.                               setup:                  O(N)
  110.                               next-state:             O(lg N)
  111.                               current-element:        O(1)
  112.                               current-element-setter: O(N)
  113.       backwards-iteration-protocol
  114.                               setup:                  O(N * lg N)
  115.                               next-state:             O(1)
  116.                               current-element:        O(1)
  117.                               current-element-setter: O(N)
  118.       random-iteration-protocol           
  119.                               setup:                  O(1)
  120.                               next-state:             O(1)
  121.                               current-element:        O(1)
  122.                               current-element-setter: O(1)
  123.       element(heap, M)                                O(M*lg N + N)
  124.       element-setter(value, heap, M)                  O(N + M*lg N + M)
  125.  
  126.   element, element-setter on arbitrary keys use the
  127.   forward-iteration-protocol (via the inherited methods), and have
  128.   accordingly bad performance.  
  129.  
  130. Self-Organizing-List
  131. --------------------
  132.   The "Self Organizing List" is a "poor man's hash table".  More precisely,
  133.   <self-organizing-list> is a subclass of <dictionary> for which addition and
  134.   retrieval are both linear in the worst case, but which use a probabilistic
  135.   strategy which yields nearly constant time in the best case.  (A
  136.   <dictionary> is a subclass of <mutable-explicit-key-collection> and
  137.   <stretchy-collection>, and is described in mindy.doc) 
  138.  
  139.   Because they have a very low overhead, self-organizing lists may provide
  140.   better peformance than hash tables in cases where references have a high
  141.   degree of temporal locality.  They may also be useful in situations where
  142.   it is difficult to create a proper hash function.  
  143.  
  144.   Define new self-organizing-lists with 
  145.  
  146.     make(<self-organizing-list>, test: test)
  147.  
  148.   Test is expected to be an equality function.  In particular, it is expected
  149.   to satisfy the identity and transitivity requirements described in chapter
  150.   5.  If not specified, test defaults to \==.  
  151.  
  152. Subseq
  153. ------
  154.   <Subsequence> is a new subclass of <sequence>.  A subsequence represents an
  155.   aliased reference to some part of an existing sequence.  Although they may
  156.   be created by make (with required keywords source:, start: and end:) on one
  157.   of the instantiable subclasses, they are more often created by calls of the
  158.   form 
  159.  
  160.     subsequence(sequence, start: 0, end: 3)
  161.  
  162.   where start: and end: are optional keywords which default to the beginning
  163.   and end, respectively, of the source sequence.  No other new operations are
  164.   defined for subsequences, since all necessary operations are inherited from
  165.   <sequence>.  
  166.  
  167.   Because subsequences are aliased references into other sequences, several
  168.   properties must be remembered:  
  169.  
  170.    1. The contents of a subsequence are undefined after any destructive
  171.       operation upon the source sequence.  
  172.    2. Destructive operations upon subsequences may be reflected in the
  173.       source.  The results of reverse! and sort! should be expected to affect
  174.       the source sequence for vector subsequences.  
  175.  
  176.   If the source sequences are instances of <vector> or <string>, then the
  177.   implementation will use subclasses of <subsequence> which are also
  178.   subclasses of <vector> or <string>.  
  179.  
  180.   Efficiency notes:  
  181.  
  182.    1. The implementation tries to insure that subsequences of subsequences
  183.       can be accessed as efficiently as the original subsequence.  (For
  184.       example, the result of 
  185.  
  186.         subsequence(subsequence(source, start: 1), start: 2)
  187.  
  188.       would produce a subsequence identical to the one produced by 
  189.  
  190.         subsequence(source, start: 3)
  191.  
  192.    2. Vector subsequences, like all other vectors, implement constant time
  193.       element access.  
  194.    3. Non-vector subsequences may take non-constant time to create, but will
  195.       provide constant-time access to the first element.  This should produce
  196.       the best performance provided some element of the subsequence is
  197.       accessed at least once.  
  198.  
  199. Vector-Search
  200. -------------
  201.   The "vector-search" module provides basic search and replace capabilities
  202.   upon restricted subsets of <sequence> -- primarily <vector>.  Exploiting
  203.   the known properties of these types yields substantially better performance
  204.   than can be achieved for sequences in  general.  
  205.  
  206.   The following functions are supplied:  
  207.  
  208.   find-first-key vector predicate? #key start end failure => key 
  209.       Find the index of first element (after start but before end) of a
  210.       vector which satisfies the given predicate.  If no matching element is
  211.       found, return failure.  The defaults for start, end and failure are,
  212.       respectively,  0, size(vector), and #f.  This function is like
  213.       find-key, but accepts start: and end: rather than skip:.) 
  214.  
  215.   find-last-key vector predicate? #key start end failure => key 
  216.       This is like find-first-key, but goes backward from end.  
  217.  
  218.